import java.util.Stack;

/**
 * @program: LeetCode
 * @description: LeetCode : 84. 柱状图中最大的矩形
 * @author: WXY
 * @create: 2023-02-03 19:15
 * @Version 1.0
 **/
public class Num084_largestRectangleArea {
    public static int largestRectangleArea1(int[] heights) {
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            int left = i;
            int right = i;
            for (; left >= 0; left--) {
                if (heights[left] < heights[i]) break;
            }
            for (; right < heights.length; right++) {
                if (heights[right] < heights[i]) break;
            }
            int weight = right - left - 1;
            int height = heights[i];
            int area = height * weight;
            max = Math.max(max, area);
        }
        return max;
    }

    public static int largestRectangleArea2(int[] heights) {
        int max = 0;
        int size = heights.length;
        int[] minRightIndex = new int[size];
        int[] minLeftIndex = new int[size];
        minLeftIndex[0] = -1;
        for (int i = 1; i < size; i++) {
            int t = i - 1;
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        minRightIndex[size - 1] = size;
        for (int i = size - 2; i >= 0; i--) {
            int t = i + 1;
            while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];
            minRightIndex[i] = t;
        }
        for (int i = 0; i < size; i++) {
            int area = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            max = Math.max(area, max);
        }
        return max;
    }

    public static int largestRectangleArea3(int[] height) {
        int max = 0;
        int[] heights = new int[height.length + 2];
        heights[0] = heights[heights.length - 1] = 0;
        for (int i = 0; i < height.length; i++) {
            heights[i + 1] = height[i];
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < heights.length; i++) {
            if (heights[i] > heights[stack.peek()]) {
                stack.push(i);
            } else if (heights[i] == heights[stack.peek()]) {
                stack.pop();
                stack.push(i);
            } else {
                while (heights[i] < heights[stack.peek()]) {
                    int curPopStackIndex = stack.pop();
                    int leftIndex = stack.peek();
                    int rightIndex = i;
                    int weight = rightIndex - leftIndex - 1;
                    int curHeight = heights[curPopStackIndex];
                    int area = weight * curHeight;
                    max = Math.max(area, max);
                }
                stack.push(i);
            }
        }


        return max;
    }


    public static int largestRectangleArea(int[] height) {
        int max = 0;
        int[] heights = new int[height.length + 2];
        heights[0] = heights[heights.length - 1] = 0;
        for (int i = 0; i < height.length; i++) {
            heights[i + 1] = height[i];
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < heights.length; i++) {
            while (heights[i] < heights[stack.peek()]) {
                int curPopStackIndex = stack.pop();
                int right = i;
                int left = stack.peek();
                int weight = right - left - 1;
                int curHeight = heights[curPopStackIndex];
                int area = weight * curHeight;
                max = Math.max(area, max);
            }
            stack.push(i);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 6, 2, 3};
        int area = largestRectangleArea(arr);
        System.out.println(area);
    }
}
